iP iwp i PMw^^ wm MAC TECHNICAL MEMORANDUM 37 REAL-TIME SIMULATION OF MffLTIDOMWKIOHAL TOTING MACHINES BY STORAGE MOBIFICATieJ! MACHIHKS A. SchHnhage December 1973 This research was supported by the Rational Science Foundation under research grant GJ-34671. MASSACHUSETTS INSTITUTE OF TECHNOLOGY PROJECT MAC CAMBRIDGE MASSACIBJSETTS 02139 REAL-TIME SIMULATION OF MULTIDIMENSIONAL TURING MACHINES BY STORAGE MODIFICATION MACHINES A „ U" i. (1) A. Schonhage 1. Introduction. In [1] the author introduced a new machine model, now called the (2) Storage Modification Machine (SMM). It was claimed, but not proved, that SMM's can simulate all sorts of Turing machines — those with multidimensional worktapes in particular -- in real time. In the following sections we describe a real-time simulation technique for keeping track of the movements of a Turing machine read-write head in the plane in such a way that repeated visits to a square are properly recognized „ This construction shows how to overcome the main difficulty in real-time simulation by SMM's of multidimensional storage devices, a difficulty which typically arises in the two-dimensional case. Furthermore, this will reinforce the intuition that such multidimensional worktapes do not possess any latent computational power. 2. The rules for real-time simulation . We consider Turing machines with one input tape, one output tape, and an initially blank storage plane with one head in start position (0,0). In a single step such a machine a) reads an input symbol, b) accesses and shifts once on its two-dimensional worktape, c) prints an output symbol, d) advances the input and output tapes one position. This work was done at the Massachusetts Institute of Technology in August, 1973. This is a preliminary, informal report meant only as a working paper. A more careful report by the author will follow. (2) An SMM constructs its own storage from an unlimited pool of nodes and arcs of bounded variety. Access is by following arcs, and an arc from an accessed node may be redirected to any other accessed node or to any new node. -2- An SMM simulates such a Turing machine "in real time" if it has the same input- output behavior as the Turing machine and there is a constant bound (not dependent on the input or time) on the number of SMM steps per Turing machine step. In other words, we allow bounded speed-up but no look-ahead. 3^ The storage reference structure . We can think of the squares of the storage plane to be represented as nodes which are arranged in a rectangular grid and which are connected to their neighbors by horizontal arcs W, N, E, S (West, North,...), as shown in Figure 1. F '■& -7 V^ s [¥,,' O \h W _^^7 It has to be understood, however, that this infinite structure does not pre- exist but has to be constructed in finite parts during the simulation. This requirement causes the main difficulty: how to decide in the case of a missing arc whether the node to which it should point has already been constructed. In view of this question, we represent the plane by an infinite sequence of such grids, which we call floors , on successively reduced scales. The ground floor F° consists of the nodes M° (z = (x,y) € z ^ horizoil tally connected as shown in Figure 1. In the same way, for k = 1,2,..., F k = {M k I z 6 Z' '} -3- From each M there is an upward arc U pointing to M , , where z = (x^y 1 ) is 2 Z obtained from z = (x,y) by x' := . (x+l)/3, y' := . (y+l)/3,. Inversely, there are nine k+1 downward arcs D ,...,D pointing from M , to the different M 's whose U-arcs i y z z k+1 point to M , , according to the pattern shown in Fig. 2. Fiq.2. D l D 2 D 3 D 4 D 5 °6 °7 D 8 °9 Thus, for example, D Q NW leads to the same node as D, . In F the D 's can ° 4 i be used to encode the information contained in the squares of the storage plane. Again we must stress that during the simulation only finite parts of the total structure described above are constructed. Arcs not yet properly connected will be pointing to their origin, thus indicating that something is missing. Initially there will be only the node M on the ground floor and no nodes on higher floors. The operations at each stage of the simulation will preserve the following: If the intended destination of any D.- arc from an installed node M (k £ 1) has been installed, then all nine destinations have been installed along with the proper connections (upward, downward, and horizontal arcs) among all ten nodes. At each stage, furthermore, the only k existing node without a properly installed U-arc will be the node M on \\J ,u ) the top floor F reached so far. The simulation process will consist of a sequence of stages. At stage t, floor k fc will be serviced , where the sequence (k ,k,k, ... )=(0, 1,0,2,0, 1,0, 3, 0,1,0,2,0,1,0,4,...) is defined recursively by for odd values of t A step of the Turing machine will be simulated each time the ground floor is serviced (i.e., in each odd stage). In the even stages the SMM will work on higher floors in order to prepare for the proper installation of the new arcs which are demanded dynamically by the movements of the storage head of the Turing machine. As servicing a floor will require only bounded time, the whole process will be a real-time simulation. 4. The stage counter . In view of the real-time requirements, we provide immediate access to the floor to be serviced at each stage by the following construction (see Fig. 3 for illustration) : At stage t = 2t the "time pointer" T is directed to C , and the "half time pointer" H is directed to C . (Initially both T and H point to C ). The new node C has to be created, with "service pointer" P directed to floor-counting node K . Then after the ground floor is serviced, another new node C _ is created. Pointers H and T are reset to HU and TUU, respectively (indicated by the dashed lines in Fig. 3), and then TP is directed to HPU (to K in Fig. 3). (The first servicing of floor j, in stage 2 J , will have created K ) Finally, floor j+1 is serviced in stage 2t + 2. -5- tu ^ ./ H Floor ( stl $ potrCl* rvd To Tke ins~W~ Ml £>or ?' Fid, 3 -6- 5. The head movements . The purpose of the H-pointers shown at the right-hand side of Fig. 3 is to simultaneously trace the movements of the Turing machine storage head on all floors already installed. Because of the reduced scales of the upper floors, however, larger delays in updating these pointers will be tolerable there. 6. Servicing floor j . Servicing consists of preparation and head adjustment . On the ground floor preparation precedes head adjustment, but on higher floors it follows head adjustment. The preparation takes place around the instantaneous head position as recorded on floor j. Let us consider this node to be the enlarged one in the center of Fig. 1. Then preparation simply means to provide the other eight nodes shown in Fig. 1 and their mutual horizontal connections; i.e., it means to check whether they already are installed and, in the case that some of them are missing, to construct the missing elements. This can be achieved in a bounded number of steps provided that either all the nodes on the next floor (floor j+1) which can be reached (*) \ ^X U-arcs from the nine nodes under preparation already have been installed along with all their horizontal connections or the enlarged node is the single node M^ n . on the top floor F J . (Note that the enlarged node need not happen to be in position D_, Fig. 2). For, in the case that (*) holds, a single U-step leads to complete information on what parts of the neighborhood already exist. In the exceptional case that floor j is the top floor so far and the enlarged node is the single node M^ . on that floor, the node M~! . and the the neighbors of M are all constructed along with all their connecting arcs. To complete the introduction of floor j+1, node K... is constructed 3+1 along with the U-arc to it, the D-arc from it, and the H-arc from it to M j+1 . (0,0) -7- Head adjustment on the ground floor takes place according to the head motion in the next step of the Turing machine computation. On other floors the head location TPH is updated to be the destination TPDHU of the U-arc from the head location on the floor below (floor j-1). (See Fig. 3.) Obviously the purpose of preparation on the ground floor is to furnish that portion of the storage plane that may be needed for the simulation of the next move by the storage head of the Turing machine. The purpose of preparation on floor j+1, on the other hand, is to enable (by condition (*) ) efficient preparation on floor j the next two times that floor is serviced. The reader should verify that condition (*) fails at no stage except for those at which the top floor is serviced. This can be shown inductively in conjunction with the additional assertion that each adjustment of a floor's H-pointer moves the pointer not more than a king's move in chess. The significant properties of the floor servicing sequence are these: (i) The first service of floor j precedes the first service of floor j+1. (ii) Floor j is serviced at most twice before floor j+1 is first serviced or between successive services of floor j+l„ 7. Conclusion . It should be obvious now how to generalize this method of real-time simulation to higher dimensions, to several heads in each of several planes, etc. Moreover, it is also possible to start with a finite amount of information already recorded in the storage plain (that is, to allow an off-line multidimensional input); then, of course, a corresponding rectangle of properly connected nodes on the ground floor should be provided as initial input to the SMM as well. Reference: [1] A. Schonhage; Universelle Turing-Speicherung. BIBLIOGRAPHIC DATA SHEET 1. Report No. NSF-OCA-GJ34671 - TM-37 2. 4. Title iiiici Subtitle Real-Time Simulation of Multidimensional Turing Machines by Storage Modification Machines 7. Author(s) A. Schb'nhage 9. Performing Organization Name and Address PROJECT MAC; MASSACHUSETTS INSTITUTE OF TECHNOLOGY: 545 Technology Square, Cambridge, Massachusetts 0213 9 12. Sponsoring Organization Name and Address Associate Program Director Office of Computing Activities National Science Foundation Washington, D. C. 20550 3. Recipient's Accession No. 5. Report Date . issued December 1973 6. 8. Performing Organization Rept. No. MAC TM-37 10. Project/Task/Work Unit No. 11. Contract/Grant No. GJ34671 13. Type of Report & Period Covered: Interim Scientific Report 14. 15. Supplementary Notes This is a preliminary, informal report meant only as a working paper. A more careful report by the author will follow. 16. Abstracts 17. Key Words and Document Analysis. 17a. Descriptors 17b. Identifiers /Open-Ended Terms 17c. COSATI Field/Group 18. Availability Statement Unlimited Distribution Write Project MAC Publications 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 9 22. Price FORM NTIS-35 (REV. 3-721 THIS FORM MAY BE REPRODUCED USCOMM-DC 14952-P72 MIT/LCS/TM-37 REAL-TIME SIMULATION OF MULTIDIMENSIONAL TURING MACHINES BY STORAGE MODIFICATION MACHINES A. Schonhage December 1973